//有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。 
//
// 跳蚤跳跃的规则如下： 
//
// 
// 它可以 往前 跳恰好 a 个位置（即往右跳）。 
// 它可以 往后 跳恰好 b 个位置（即往左跳）。 
// 它不能 连续 往后跳 2 次。 
// 它不能跳到任何 forbidden 数组中的位置。 
// 
//
// 跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。 
//
// 给你一个整数数组 forbidden ，其中 forbidden[i] 是跳蚤不能跳到的位置，同时给你整数 a， b 和 x ，请你返回跳蚤到家的最少跳跃
//次数。如果没有恰好到达 x 的可行方案，请你返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
//输出：3
//解释：往前跳 3 次（0 -> 3 -> 6 -> 9），跳蚤就到家了。
// 
//
// 示例 2： 
//
// 
//输入：forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
//输出：-1
// 
//
// 示例 3： 
//
// 
//输入：forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
//输出：2
//解释：往前跳一次（0 -> 16），然后往回跳一次（16 -> 7），跳蚤就到家了。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= forbidden.length <= 1000 
// 1 <= a, b, forbidden[i] <= 2000 
// 0 <= x <= 2000 
// forbidden 中所有位置互不相同。 
// 位置 x 不在 forbidden 中。 
// 
//
// Related Topics 广度优先搜索 数组 动态规划 👍 184 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2023-08-30 21:00:45
 * @description 1654.到家的最少跳跃次数
 */
public class MinimumJumpsToReachHome{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new MinimumJumpsToReachHome().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*bfs,但需要确定上界，分三种情况
		 * 第一种a=b,则最远为x
		 * 第二种a>b，最远为x+b
		 * 第三种,max(a+b+max(forbidden),x)
		 * 证明，将区域分为，禁止区，安全区不包括forbidden，和界外区
		 * 通过图形变换，可以得到任意一次需要出界的路径，都可以转化为一次不出界的路径
		 * 则最大上界就是上式*/
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
		//bfs辅助
		Queue<int []>q= new LinkedList<>();
		//访问过的节点
		Set<Integer> visi=new HashSet<Integer>();
		//三个值，第一位0表示当前位置，1.表示前进得到，-1表示后退得到,第三个位置代表步骤数
		q.offer(new int[]{0,1,0});
		//0号位置已经访问
		visi.add(0);
		int l=0;
		//把所有的上界都设置为最大的一种情况
		int r=Math.max(Arrays.stream(forbidden).max().getAsInt()+a,x)+b;
		//把forbidden放入set种方便快速查询
		Set<Integer> forbiddenSet=new HashSet<Integer>();
		for (int i : forbidden) {
			forbiddenSet.add(i);
		}
		//把每一步放入队列中，
		while (!q.isEmpty()){
			int[] poll = q.poll();
			int pos=poll[0],direction=poll[1],step=poll[2];
			//如果到了，直接返回
			if(pos==x){
				return step;
			}
			// 下一次前进后的坐标
			int nextPos=pos+a;
			// 如果下一次方向为前进
			int nextDirection=1;
			//前进的情况
			// 没有超出边界 && 没有前进到达过这个位置 && 这个坐标不是不可到达点
			if(l<=nextPos&&nextPos<=r&&!visi.contains(nextPos*nextDirection)&&!forbiddenSet.contains(nextPos)){
				visi.add(nextPos*nextDirection);
				q.offer(new int[]{nextPos,nextDirection,step+1});
			}
			//只有当当前位置是前进来的时候才可以后退，后退的情况
			if(direction==1){
				nextPos=pos-b;
				nextDirection=-1;
				// 没有超出边界 && 没有后退到达过这个点 && 这个点不是不可到达点
				if(l<=nextPos&&nextPos<=r&&!visi.contains(nextDirection*nextPos)&&!forbiddenSet.contains(nextPos)){
					visi.add(nextPos*nextDirection);
					q.offer(new int[]{nextPos,nextDirection,step+1});
				}
			}
		}
		return -1;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
